package org.example.DataStructure.Stack;

import java.util.EmptyStackException;

//栈的实现
public class Stack<T> {
    //创建内部节点类
    private static class Node<T> {
        //成员变量
        T data;
        Node<T> next;

        //构造方法
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    //成员变量
    //记录头节点,栈顶的前一个节点
    private Node<T> head;
    //记录当前栈的节点个数
    private int size;

    //构造方法
    public Stack() {
        //初始化栈顶,且设置栈顶存储数据为空
        head = new Node<>(null, null);
        //初始化栈中数据元素的个数
        size = 0;
    }

    //判断栈是否为空，返回布尔值
    public boolean isEmpty() {
        return size == 0;
    }

    //获取栈中元素的个数
    public int size() {
        return size;
    }

    //弹出栈顶元素并返回
    public T pop() {
        //空指针判断
        if (head.next == null) {
            return null;
        }
        //记录弹出的值
        T data = head.next.data;
        //改变头结点的next指针
        head.next = head.next.next;
        //将元素数量-1
        size--;
        //返回弹出的值
        return data;
    }

    //向栈中压入元素T
    public void push(T data) {
        //构建新节点储存元素,并指向头节点的下一个节点
        Node<T> node = new Node<>(data, head.next);
        //将头节点的指针指向新节点
        head.next = node;
        //将元素数量+1
        size++;
    }

    //查看栈顶元素但是并不弹出
    public T peek() {
        if (head.next == null) {
            return null;
        } else {
            return head.next.data;
        }
    }

    //重写ToString方法
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("栈顶:");
        for (Node<T> node = head.next; node != null; node = node.next) {
            sb.append(node.data).append(" ");
        }
        sb.append("栈底");
        return sb.toString();
    }
}
